//package 力扣.排序.合并排序;
//
//import java.util.List;
//
//public class 排序链表148 {
//    class ListNode {
//        int val;
//        ListNode next;
//        ListNode(int x) { val = x; }
//    }
//
//    /** 原理：合并排序
//     *
//     *
//     */
//    public ListNode sortList(ListNode head) {
//        return msort(head);
//    }
//
//    private ListNode msort(ListNode root){
//          if (root == null || root.next == null){//空链表、单个链表不用排序
//              return root;
//          }
//          ListNode midpre = getMid(root);//寻找中间节点的前驱节点
//          ListNode mid = midpre.next;
//          midpre.next = null;//要拆分两个链表，一定要从中间节点这里断开
//          //递归进入左右子树
//          ListNode l = msort(root);
//          ListNode r = msort(mid);
//          //合并左右子树
//          ListNode l1 = l;
//          ListNode l2 = r;
//          ListNode dummy = new ListNode(0);
//          ListNode tmp = dummy;
//          while (l1 != null || l2 != null){
//              if (l2 == null || (l1 != null && l1.val <= l2.val)){
//                  tmp.next = l1;
//                  l1 = l1.next;
//                  tmp = tmp.next;
//              }else {
//                  tmp.next = l2;
//                  l2 = l2.next;
//                  tmp = tmp.next;
//              }
//          }
//          tmp.next = null;//别忘了给尾节点指空（养成好习惯）
//          return dummy.next;
//    }
//    private ListNode getMid(ListNode head){//栈溢出
//        ListNode slow = head;
//        ListNode fast = head;
//        ListNode pre = head;
//        while (fast != null && fast.next != null){
//            fast = fast.next.next;
//            pre = slow;
//            slow = slow.next;
//        }
//        return fast == null ? pre : slow;
//    }
//
//
//    // 这里涉及到考点，找到一个链表的中间点
//    private ListNode findMiddle(ListNode head) {
//        ListNode s1 = head;
//        ListNode s2 = head;
//        ListNode pre = s1;
//        while (s2 != null && s2.next != null) {
//            pre = s1;
//            s1 = s1.next;
//            s2 = s2.next.next;
//        }
//        return s2 != null ? s1 : pre;
//    }
//
//    private ListNode mergeSort(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        }
//
//        // 与二叉树相比，这里需要把一个链表拆分成两部分
//        // 二叉树直接可以通过root.left/root.right得到
//        // 链表没有那么方便。
//        ListNode mid = findMiddle(head);
//        ListNode back = mid.next;
//        mid.next = null;
//
//        // 后序遍历左右两个链表
//        ListNode i = mergeSort(head);
//        ListNode j = mergeSort(back);
//
//        // 遍历完成之后，开始将两个有序链表进行合并
//        // 这里涉及到考点, dummy head.
//        ListNode dummy = new ListNode(0);
//        ListNode tail = dummy;
//
//        // 这里是合并两个有序链表的模板
//        while (i != null || j != null) {
//            if (j == null || i != null && i.val <= j.val) {
//                tail.next = i;
//                tail = i;
//                i = i.next;
//            } else {
//                tail.next = j;
//                tail = j;
//                j = j.next;
//            }
//        }
//        tail.next = null;
//
//        // 返回信息合并之后的结果
//        return dummy.next;
//    }
//
//
//    public ListNode sortList2(ListNode head) {
//         if (head == null){
//             return null;
//         }
//         msort2(head);
//         return head;
//    }
//    private void msort2(ListNode head) {
//        if (head == null || head.next == null){
//            return;
//        }
//        ListNode mid = findMiddle2(head);
//        msort2();
//    }
//
//    private ListNode findMiddle2(ListNode head) {
//        ListNode l1 = head;
//        ListNode l2 = head;
//        ListNode pre = head;
//        while (l2 != null && l2.next != null){
//            pre = l1;
//            l1 = l1.next;
//            l2 = l2.next.next;
//        }
//        return l2 == null ? pre : pre.next;
//
//    }
//}
